package 分治.快排;

import java.util.Random;
// 首先用快排快速分区，然后根据情况讨论，讨论出 k 在哪个区，然后把那个区再排一下（优化）
//  然后递归处理
public class 最小的k个数40 {

    public int [] findkthMin(int [] arr,int k){
         qsort(arr,0,arr.length-1,k);

         int [] ret = new int[k];
         for(int i = 0 ; i < k ;i++)
             ret[i] = arr[i];
         return ret;

    }
    public void qsort(int [] arr,int l,int r,int k){
        if(l>=r) return;
        int left = l-1,right = r+1,i = l;
        int index = arr[new Random().nextInt(r-l+1)+l];
        while(i<right)
        {
            if(arr[i] > index) swap(arr,--right,i);
            else if (arr[i]< index) swap(arr,++left,i++);
            else i++;
        }
        // [l,left] [left+1,right-1] [right,r]
        int a = left-l+1,b = right-left-1,c = r-right+1;
        if(a >= k)   qsort(arr,l,left,k);
        else if (b+a>=k) return ;
        else qsort(arr,right,r,k-a-b);


    }

    public void swap(int []arr,int j ,int k){
        int temp = arr[j];
        arr[j] = arr[k];
        arr[k] = temp;
    }

}
